package BinaryTree.BinarySearchTree;

import java.util.*;

/**
 * @author shy_black
 * @date 2019/4/21 13:07
 * @Description:
 */
public class BST<E extends Comparable<E>> {
    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {

        return size == 0;

    }

    public void add(E e) {
        root = add(root, e);
//        if(root == null) {
//            root = new Node(e);
//            size++;
//        }
    }

    //向以node为根的二分搜索树中插入元素E,递归算法
    //1.每次比较e与node.e的大小，
    // 递归：如果新增元素e小于node.e，就把e与node的左子树比较
    //      如果新增元素饿大于node.e，就把e与node的右子树比较
    //递归结束：当遇到左子树或右子树为空时，将元素e包装为节点，
    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        return node;
//        if(e.equals(node.e))
//            return ;
//        else if(e.compareTo(node.e) < 0 && node.left == null) {
//            node.left = new Node(e);
//            size++;
//            return;
//        }
//        else if(e.compareTo(node.e) > 0 && node.right == null) {
//            node.right = new Node(e);
//            size++;
//            return;
//        }
//        if(e.compareTo(node.e) < 0) {
//            add(node.left,e);
//        }
//        else {
//            add(node.right,e);
//        }
    }
    //查询元素

    /**
     * @param e:查找是否有元素e
     * @return
     */
    public boolean contains(E e) {

        return contains(root, e);
    }

    private boolean contains(Node node, E e) {
        if (node == null)
            return false;

        if (e.compareTo(node.e) == 0)
            return true;
        else if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        } else //e>node.e
            return contains(node.right, e);
    }

    //BST的前序遍历
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
//        if(node == null)
//            return ;
        if (node != null) {
            System.out.println(node.e);
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    //BST的中序遍历

    public void midOrder() {
        midOrder(root);
    }

    private void midOrder(Node node) {
        if (node != null) {
            midOrder(node.left);
            System.out.println(node.e);
            midOrder(node.right);
        }
    }

    //BST的后序遍历
    public void lastOrder() {
        lastOrder(root);
    }

    private void lastOrder(Node node) {
        if (node != null) {
            lastOrder(node.left);
            lastOrder(node.right);
            System.out.println(node.e);
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }

    //层序遍历
    public void levelOrder() {
        levelOrder(root);
    }

    private void levelOrder(Node node) {
        if (node == null)
            return;
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.remove();
            System.out.print(cur.e);
            if (cur.left != null)
                queue.add(cur.left);
            if (cur.right != null)
                queue.add(cur.right);
        }
    }

    //移除最小元素节点
    public E removeMin() {
        E ret = minmum();
        root = removeMin(root);
        return ret;
    }
    //返回删除节点后新的二分搜索树的根
    private Node removeMin(Node node) {
        if(node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    public E minmum() {
        if (size == 0) {
            return null;
            //throw new IllegalArgumentException("BST为空");
        }
        Node minNode = minmum(root);

        return minNode.e;
    }

    private Node minmum(Node node) {
        if (node.left == null)
            return node;
        return minmum(node.left);
    }

    //删除最大值元素的节点
    public E removeMax() {
        E ret = maxmum();
        root = removeMax(root);
        return ret;
    }
    private Node removeMax(Node node) {
        if(node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        //将当前节点的右子树进行删除操作，并将结果返回个当前节点的右子树
        node.right =  removeMax(node.right);
        return node;
    }

    //寻找最大元素
    public E maxmum() {
        if(size == 0) {
            throw new IllegalArgumentException("BST为空");
        }
        return maxmum(root).e;
    }
    private Node maxmum(Node node) {
        if(node == null)
            return node;
        return maxmum(node.right);
    }


    /**
     * 删除指定节点
     * 删除左右都有孩子的节点d
     * 找到s = min(d->right)
     * s 是 d的后继
     * s->right = delMin（d->right）
     * s->left = d->left
     * 删除d ,s 是新的子树的根
     */
    //提供一个给用户方便使用的方法，在这个方法中调用私有方法
    public void remove(E e) {
        remove(root,e);
    }
    //删除以node为根的二分搜索树中值为e的节点，递归算法
    //返回删除节点后新的二分搜索树的根

    /**
     *
     * @param node
     * @param e
     * @return
     * 逻辑：当root为空时，直接返回null
     * 当待删除元素e小于当前节点元素时，找当前元素的左子树，递归
     * 当待删除元素e大于当前节点元素时，找当前元素的右子树，递归
     * 当待删除元素e正好等于当前元素节点时，开始删除操作
     *  ：如果当前元素的左子树为空，那么直接将右节点作为子树，替换当前元素的位置
     *  ：如果当前元素的右子树为空，那么直接将左节点作为子树，替换当前元素的位置
     *  ：如果当前元素左右子树都不为空，那么就
     *      寻找当前元素的右子树的最小节点，保存为successor
     *      删除当前元素右子树的最小节点successor，并将删除后的树链接为为successor的右子树，
     *      将当前节点的左子树连接到successor上。
     *  逻辑结束。
     */
    private Node remove(Node node,E e) {
        if(node == null)
            return null;
        if(e.compareTo(node.e) < 0) {
            node.left = remove(node.left,e);
            return node;
        }else if(e.compareTo(node.e) > 0) {
            node.right = remove(node.right,e);
            return node;
        }else {//e == node.e
            if(node.left == null) {
                Node rightNdoe = node.right;
                node.right = null;
                size--;
                return rightNdoe;
            }
            if(node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            //待删除左右子树均不为空
            //找到比代删除节点大的的最小节点，即待删除节点右子树的最小节点
            //用这个节点替代待删除节点的位置
            Node successor = minmum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            successor.left = node.left;
            node.left = node.right = null;
            return successor;
        }

    }



    /**
     * @param node：递归传入的节点
     * @param depth：当前深度
     * @param res：StringBuilder型的字符串，当generateBSTString执行完毕后，最后res的结果即为二叉搜索树的图像版 5
     *                                                                           -3
     *                                                                           --2
     *                                                                           ---null
     *                                                                           ---null
     *                                                                           --4
     *                                                                           ---null
     *                                                                           ---null
     *                                                                           -6
     *                                                                           --null
     *                                                                           --8
     *                                                                           ---null
     *                                                                           ---null
     */
    private void generateBSTString(Node node, int depth, StringBuilder res) {
        if (node == null) {
            res.append(generateDepthString(depth) + "null\n");
            return;
        }
        res.append(generateDepthString(depth) + node.e + "\n");
        generateBSTString(node.left, depth + 1, res);
        generateBSTString(node.right, depth + 1, res);
    }

    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++)
            res.append("-");
        return res.toString();

    }


    public static void main(String[] args) {
//        BST<Integer> bst = new BST<>();
//        int[] nums = {5, 3, 6, 8, 4, 2};
//        for (int num : nums) {
//            bst.add(num);
//        }
//        bst.midOrder();
//        System.out.println("-----层序遍历-----");
//        bst.levelOrder();


        //System.out.println();
        //System.out.println(bst);


        //测试最大最小值得删除
        BST<Integer> b = new BST<>();
        Random random = new Random();
        int n = 10000;
        for(int i = 0;i < n;i++)
            b.add(random.nextInt(n));
        LinkedList<Integer> list = new LinkedList<>();
        while(!b.isEmpty())
            list.add(b.removeMin());
        System.out.println(list);
        for(int i = 1;i < list.size();i++)
            if(list.get(i-1) > list.get(i)) {
                System.out.println("删除最小值方法有问题！！！");
                return;
            }
        System.out.println("删除最小值方法测试成功！！！");











//        BST<Integer> bst_1 = new BST<>();
//        Random random = new Random();
//        int n = 10000;
//        for(int i = 0;i < n;i++)
//            bst_1.add(random.nextInt(n));
//        ArrayList<Integer> list = new ArrayList<>();
//        while(!bst_1.isEmpty())
//            list.add(bst_1.removeMin());
//        System.out.println(list);
//
//        for(int i = 1;i < list.size();i++) {
//            if(list.get(i-1) > list.get(i)) {
//                System.out.println("删除方法错误");
//                return;
//            }
//        }
//        System.out.println("测试成功！！！");
//

    }


}
